package com.atwy.graph.uf;

/**
 * 并查集的最终形态
 * 主要还是针对find函数的优化。
 *
 * 相比路径压缩，find函数的性能提升了
 */
public class UF_Final implements UFInterface{
    /** 统计连通分量个数 */
    private int count;
    /** 节点 x 的父节点是 parent[x] */
    private int[] parent;

    public UF_Final(int n) {
        this.count = n;
        this.parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    @Override
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP != rootQ) {
            count--;
            parent[rootP] = rootQ;
        }
    }

    private int find(int x) {
        if(parent[x]!=x){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    @Override
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    @Override
    public int count() {
        return this.count;
    }
}
